package com.shm.leetcode;

/**
 * 647. 回文子串
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 *
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 *
 *
 *
 * 示例 1：
 *
 * 输入："abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 * 示例 2：
 *
 * 输入："aaa"
 * 输出：6
 * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 *
 *
 * 提示：
 *
 * 输入的字符串长度不会超过 1000 。
 * @author SHM
 */
public class CountSubstrings {
    /**
     * 方法一：中心拓展
     * 思路与算法
     *
     * 计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：
     *
     * 枚举出所有的子串，然后再判断这些子串是否是回文；
     * 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。
     * 假设字符串的长度为 nn。我们可以看出前者会用 O(n^2)O(n
     * 2
     *  ) 的时间枚举出所有的子串 s[l_i \cdots r_i]s[l
     * i
     * ​
     *  ⋯r
     * i
     * ​
     *  ]，然后再用 O(r_i - l_i + 1)O(r
     * i
     * ​
     *  −l
     * i
     * ​
     *  +1) 的时间检测当前的子串是否是回文，整个算法的时间复杂度是 O(n^3)O(n
     * 3
     *  )。而后者枚举回文中心的是 O(n)O(n) 的，对于每个回文中心拓展的次数也是 O(n)O(n) 的，所以时间复杂度是 O(n^2)O(n
     * 2
     *  )。所以我们选择第二种方法来枚举所有的回文子串。
     *
     * 在实现的时候，我们需要处理一个问题，即如何有序地枚举所有可能的回文中心，我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数，那么回文中心是一个字符；如果回文长度是偶数，那么中心是两个字符。当然你可以做两次循环来分别枚举奇数长度和偶数长度的回文，但是我们也可以用一个循环搞定。我们不妨写一组出来观察观察，假设 n = 4n=4，我们可以把可能的回文中心列出来：
     *
     * 编号 ii	回文中心左起始位置 l_il
     * i
     * ​
     *  	回文中心右起始位置 r_ir
     * i
     * ​
     *
     * 0	0	0
     * 1	0	1
     * 2	1	1
     * 3	1	2
     * 4	2	2
     * 5	2	3
     * 6	3	3
     * 由此我们可以看出长度为 nn 的字符串会生成 2n-12n−1 组回文中心 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ]，其中 l_i = \lfloor \frac{i}{2} \rfloorl
     * i
     * ​
     *  =⌊
     * 2
     * i
     * ​
     *  ⌋，r_i = l_i + (i \bmod 2)r
     * i
     * ​
     *  =l
     * i
     * ​
     *  +(imod2)。这样我们只要从 00 到 2n - 22n−2 遍历 ii，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n^2)O(n2)。
     * 空间复杂度：O(1)O(1)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        int n = s.length(), ans = 0;
        for(int i=0;i<2*n-1;i++){
            int l = i/2,r = i/2 + i%2;
            while(l>=0&&r<n&&s.charAt(l)==s.charAt(r)){
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }

    /**
     * 方法一：暴力法主要浪费在判断回文串上，不能有效利用同中心的回文串的状态，简单来说就是此时我们假设前面的子串s[j,i]是回文串，那么，子串s[j-1,i+1]也有可能是回文串，不难想出当且仅当子串s[j,i]是回文串且s[j-1]=s[i+1]时，子串s[j-1,i+1]也是回文串，于是我们可以通过数组保存子串是否是回文串，然后通过递推上一次的状态，得到下一次的状态，属于动态规划的解法，令dp[j][i]表示子串s[j,i]是否是回文串，状态转移如下：
     *
     * 当i=j时，单个字符肯定是回文串，可以看成奇数回文串的起点
     * 当s[i]=s[j]且i-j=1，则dp[j][i]是回文串，可以看成偶数回文串的起点
     * 当s[i]=s[j]且dp[j+1][i-1]是回文串，则dp[j][i]也是回文串
     * 其他情形都不是回文串
     * 其中条件1、2、3是可以合并的：
     *
     * 当s[i]=s[j]时，dp[j+1][i-1]是回文串或i-j<2，则dp[j][i]也是回文串
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n^2)O(n
     * 2
     *  )
     * 空间复杂度：O(n^2)O(n
     * 2
     *  )
     * 作者：tinylife
     * 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/jian-dan-de-dong-tai-gui-hua-si-xiang-by-tinylife/
     * @param s
     * @return
     */
    public int countSubstrings_2(String s) {
        int n = s.length(), ans = 0;
        boolean[][] dp = new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                if(s.charAt(i)==s.charAt(j)&&(i-j<2 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    ++ans;
                }
            }
        }
        return ans;
    }


    /**
     * 方法二：动态规划的思想优点是比较好想，缺点也很明显，空间复杂度比较高，那么回顾一下，我们只是需要得到同中心的回文子串数目，显然只要我们找到子串的中心，然后使用两个指针不断向两端延伸即可，也就是中心扩展法，这样空间复杂度就降到O(1)了。找中心很简单，字符串中的元素逐一遍历即可，但是要注意是奇数还是偶数回文串，奇数回文串中心只有一个，而偶数回文串中心有两个，我们事先不知道奇偶，解决办法可以参考官方题解的，也可以都计算一遍，这样比较好想。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n^2)O(n
     * 2
     *  )
     * 空间复杂度：O(1)O(1)
     * 作者：tinylife
     * 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/jian-dan-de-dong-tai-gui-hua-si-xiang-by-tinylife/
     */
    public int countSubstrings_3(String s) {
        int n = s.length(), ans = 0;
        for(int i=0;i<n;i++){
            ans = midExtend(s,i,i,ans,n);
            ans = midExtend(s,i,i+1,ans,n);
        }
        return ans;
    }

    public int midExtend(String s,int i,int j,int res,int n){
        while(i>=0&&j<n&&s.charAt(i)==s.charAt(j)){
            --i;
            ++j;
            ++res;
        }
        return res;
    }
}
